package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/27/20
 * @Version 1.0
 */

import java.util.Arrays;

/**
 * 插入排序
 * 相当于把待排序序列分成已排序区和未排序区
 *  每趟排序都将从未排序区选择一个元素插入到已经排序合适的位置
 *  假设第一个元素属于已排序区,那么还要插入len-1趟
 *
 *  原地算法
 *  稳定排序
 *  时间复杂度,最好是O(n),最坏是O(n^2),平均是O(n^2)
 *
 * @author jane
 */
public class InsertionSort {

    /**
     * 小的往前排
     * @param arr
     * @return
     */
    public static int[] sortUp(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }

        int length = arr.length;

        for(int i=0;i<length-1;i++){
            for(int j=i;j>=0;j--){
                if(arr[j+1]<arr[j]){
                    int temp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }else{
                    break;
                }
            }
        }

        return arr;
    }


    /**
     * 大的往前排
     * @param arr
     * @return
     */
    public static int[] sortDown(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }

        for(int i=0;i<arr.length-1;i++){
            int temp=arr[i+1];
            int j;
            for(j=i;j>=0;j--){
                if(temp>arr[j]){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            if(j!=i){
                arr[j+1]=temp;
            }
        }
        return arr;
    }


    /**
     * 带哨兵,多加一个a[0]用于存储待插入数,小的往前排
     * @param arr
     * @return
     */
    public static int[] sortUpBySentinel(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }
        int[] arrSentinel=new int[arr.length+1];
        arrSentinel[0]=0;
        System.arraycopy(arr,0,arrSentinel,1,arr.length);
        int arrLength = arr.length;
        for(int i=1;i<arrLength;i++){
            arrSentinel[0]=arr[i];
            int j=i;
            while (arrSentinel[0]<arrSentinel[j]){
                arrSentinel[j+1]=arrSentinel[j];
                j--;
            }
            if(j!=i){
                arrSentinel[j+1]=arrSentinel[0];
            }
        }
        return Arrays.copyOfRange(arrSentinel,1,arrSentinel.length);
    }


    /**
     * 带哨兵,多加一个a[0]用于存储待插入数,大的往前排
     * @param arr
     * @return
     */
    public static int[] sortDownBySentinel(int[] arr){
        if(arr==null||arr.length<2){
            return arr;
        }

        int arrLength = arr.length;
        int[] arrSentinel = new int[arrLength+1];
        System.arraycopy(arr,0,arrSentinel,1,arrLength);
        for(int i=1;i<arrLength;i++){
            int cur = arrSentinel[0]=arr[i];
            int j=i;
            while(cur>arrSentinel[j]){
                arrSentinel[j+1]=arrSentinel[j];
                j--;
            }
            if(j!=i){
                arrSentinel[j+1]=cur;
            }
        }
        return Arrays.copyOfRange(arrSentinel,1,arrSentinel.length);
    }
}
